<改变未来的算法> 笔记

搜索引擎

简要的说，一次搜索包含了: 匹配，排名。

匹配

这里的主要概念就是索引。（想象一下字典） 首先需要知道词出现在哪里

建立词表，记录每个词出现的地方（页面）

当进行多词搜索，进行多次匹配也就可以了。但是，如果需要进行连续词搜索，那我们还需要知道词的位置。

索引信息中记录词的位置（第1个，第10个，。。。）

这个做完了之后，我们还可以进行元词搜索，考虑当前html的结构，=<title>=,=<body>=等标签，记录开始和闭合的节点问题，即可进行例如=key:inTitle=类型的搜索

PageRank

排名

匹配完成后，还有一个重要的事情就是排名，找到最接近查找的内容。但是同样一个词，计算机如何去理解什么是最接近的? 可选的办法就是：*权重，计分*

  • 计分:

考虑使用引用次数进行计分，亦即页面超链接在其他页面中的次数。

  • 权重:

1000个人引用的网页和1个人引用的网页，其内容的权威程序大体上也应该可以体现。

将页面权重设置为所有引用其页面的页面权重之和

以上看起来像解决了问题，但是这样，会出现一个问题，=循环引用=–cycle

随机访问者算法。

公钥加密

当信息交换双方协商好一种加密密钥（类似加密字典）,简单的加密也就可以进行了。下面探讨的主要是，如何公共的协商出一种密钥。

  1. 首先考虑一个问题，如何利用公共的信息得到一个秘密。假设有这种一个操作可以。那:

操作本身可交换（协议双方的操作顺序无关）,操作本身不可逆（不唯一） 

3 mod 11 = 3; 5 mod 11 = 5; (3*5) mod 11 = (3 mod 11) * 5 = (5 mod 11) * 3 = 4

  1. 假定该操作为'*',协议双方选择一种公钥p，个人私钥p1,p2(只有自己知道)

    p * p1 = r1; p * p2 = r2; key = r1 * p2 = r2 * p1

这样就得出了只有协议双方才知道的密钥key.

以上的操作很类似于抽象代数里的群。

纠错码

本质而言，我理解，就是冗余信息进行容错。

  1. 简单校验和。（checkSum）
  2. 阶梯校验和。（通过位置+值计算）
  3. 将校验和进行二维应用，即可定位到错误的地方。

图形识别

主要模式就是 1. 训练 2. 分类

  1. 邻近者模式 > 对每个像素做异或，寻找差异最小的模式
  2. 决策树 > 学习过程没有太明白，分类就按照决策树遍历即可。
  3. 神经网络 > 学习过程同样没有太明白。分类：现实问题作为输入映射到神经元，神经元的阀值触发信号，汇聚到下一级神经元，一直到最终决定。

数据压缩

本质上就是查找重复模式

无损压缩

  1. 同前
  2. 根据词频进行更短符号
  3. TODO 霍夫曼编码

有损压缩

  1. 图片（隔行列删除像素信息）
  2. JPEG（像素块内寻找模式-比如分成8*8的块状信息体）

数据库

  1. 事物 作为待办事项，写redo-log，保证操作幂等。
  2. 复制提交
  3. 回滚
  4. 预备提交
  5. 虚表

数字签名

TODO 再仔细看一看

不可判定问题

构造冲突的命题

  1. 构造一类程序用于判断程序是否会崩溃

canCrash—>canCrashWired—>crashOnSelf—>antiCrashOnSelf 

|          | canCrash | canCrashWired | crashOnSelf | antiCrashOnSelf |
|----------+----------+---------------+-------------+-----------------|
| 输入条件 | 程序     | 程序          | 自身        | 自身            |
| 能崩溃   | yes      | 崩溃          | 崩溃        | yes             |
| 不能崩溃 | no       | no            | no          | 崩溃            |
|----------+----------+---------------+-------------+-----------------|